{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"https://raw.githubusercontent.com/Qiskit/qiskit-tutorials/master/images/qiskit-heading.png\" alt=\"Note: In order for images to show up in this jupyter notebook you need to select File => Trusted Notebook\" width=\"500 px\" align=\"left\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# _*Quantum support vector machine*_ \n",
    "\n",
    "***\n",
    "### Contributors \n",
    "Shan Jin, Xi He, Xiaokai Hou, Li Sun, Dingding Wen, Shaojun Wu and Xiaoting Wang$^{1}$\n",
    "\n",
    "1. Institute of Fundamental and Frontier Sciences, University of Electronic Science and Technology of China，Chengdu, China，610051\n",
    "***"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Introduction\n",
    "In machine learning, support vector machines (SVMs, also supporting vector networks) are supervised learning models related to related learning algorithms that can analyze data, identify patterns, and use for classification and regression analysis. Given a set of training samples, each marked as belonging to two classes, an SVM training algorithm builds a model and assigns a new instance as a class or other class, making it a non-probabilistic binary linear classification. An example of an SVM model, such as a point in space, maps such that the different categories of the examples are represented by an apparent gap that is as wide as possible. The new embodiments are then mapped into the same space and the prediction belongs to a category based on their falling on the gap side.<br \\>\n",
    "In addition to linear classification, support vector machines can use so-called kernel methods whose inputs are implicitly mapped into high-dimensional feature spaces for efficient nonlinear classification.\n",
    "\n",
    "#### Experiment design\n",
    "The goal of the SVM algorithm is to classify a new vector $x_0$ into one of two classes by the labeled training samples. A maximum-margin hyperplane will be found to divide the training samples in the training process. We construct the hyperplane which subject to the constraints $y_i(wx_i + b) \\geq 1$ for all $i$($w = \\sum_{i=1}^{M}\\alpha_i x_i$, $\\alpha_i$ is the weight for the $i$ th training vector $x_i$). We can get the parameters $b$ and $\\alpha_i$ by solving the linear equation $F(b, \\alpha_1, \\alpha_2, ..., \\alpha_M)^T$ $= (0, y_1, y_2, ..., y_M)^T$($F$ is a $(M+1)\\times(M+1)$ matrix).<br \\>\n",
    "(1).Employ the matrix inversion $|b, a\\rangle = \\tilde F|y\\rangle$, where $\\tilde F = F/trF$. We can transform the quantum state to $|b, a\\rangle = \\frac{1}{\\sqrt{N_{b,a}}}(b|0\\rangle + \\sum_{k=1}^{M}\\alpha_i |i\\rangle)$ ($N_{b,a}$ and $N_{0,y}$ are normalization factors.) <br \\>(2).With the optimized parameters $b$ and $\\alpha_i$, the classification results $y(x_0) = sgn(\\sum_{i=1}^{M}\\alpha_i(x_i\\cdot x_0) + b)$. Apply the training-data oracle to prepare the training-data state $|\\tilde u\\rangle$($|\\tilde u \\rangle = \\frac{1}{\\sqrt{N_{\\tilde u}}}(b|0\\rangle|0\\rangle + \\sum_{k=1}^{M}\\alpha_k|x_k||k\\rangle|x_k\\rangle)$ with $N_{\\tilde u} = b^2 + \\sum_{k=1}^{M}\\alpha_k^{2}|x_k|^2$). In addition, construct the query state: $|\\tilde x\\rangle = \\frac{1}{\\sqrt{N_{\\tilde x}}}(|0\\rangle|0\\rangle + \\sum_{k=1}^{M}|x||k\\rangle|x\\rangle)$ with $N_{\\tilde x} = M|x|^2 + 1$. (3).Perform a swap test. We construct the state $|\\psi\\rangle = \\frac{1}{\\sqrt{2}}(|0\\rangle|\\tilde u\\rangle + |1\\rangle|\\tilde x\\rangle)$ and measure the ancilla in the state $|\\phi\\rangle = \\frac{1}{\\sqrt{2}}(|0\\rangle - |1\\rangle)$. The success probability $P = |\\langle\\psi|\\phi\\rangle|^2 = \\frac{1}{2}(1-\\langle \\tilde u | \\tilde x)$. If $P<1/2$, $|x\\rangle$ is classified as $+1$, otherwise $-1$.\n",
    "\n",
    "#### Quantum SVM circuit\n",
    "Due to limited time, the circuit of the quantum SVM algorithm has not been completed. We will submit QISKIT version of Quantum Support Vector Machine in the follow-up work."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<h2>Version information</h2>\n",
       "<p>Please note that this tutorial is targeted to the <b>stable</b> version of the QISKit SDK. The following versions of the packages are recommended:</p>\n",
       "<table>\n",
       "<tr><th>Package</th><th colspan=\"2\">Version</th></tr>\n",
       "<tr><td>QISKit</td><td> 0.4.8</td></tr>\n",
       "<tr><td>IBMQuantumExperience</td><td>&gt;= 1.8.26</td></tr>\n",
       "<tr><td>numpy</td><td>&gt;= 1.13, &lt; 1.14</td></tr>\n",
       "<tr><td>scipy</td><td>&gt;= 0.19, &lt; 0.20</td></tr>\n",
       "<tr><td>matplotlib</td><td>&gt;= 2.0, &lt; 2.1</td></tr>\n",
       "</table>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%run ../version.ipynb"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
